package com.future;

import java.util.*;

/**
 * Description: 146. LRU ����
 * ��ˢ���19 NodeDoubleLinkedList
 *
 * @Author: future
 * @Date:2022/5/27:0:31
 */
public class Solution_146 {

    public static void main(String[] args) {
        DoubleLinked lRUCache = new DoubleLinked(2);
        lRUCache.put(1, 1); // ������ {1=1}
        lRUCache.put(2, 2); // ������ {1=1, 2=2}
        lRUCache.get(1);    // ���� 1
        lRUCache.put(3, 3); // �ò�����ʹ�ùؼ��� 2 ���ϣ������� {1=1, 3=3}
        lRUCache.get(2);    // ���� -1 (δ�ҵ�)
        lRUCache.put(4, 4); // �ò�����ʹ�ùؼ��� 1 ���ϣ������� {4=4, 3=3}
        lRUCache.get(1);    // ���� -1 (δ�ҵ�)
        lRUCache.get(3);    // ���� 3
        lRUCache.get(4);    // ���� 4
        /**
         * ["LRUCache","put","put","get","put","get","put","get","get","get"]
         * [[2],[1,0],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
         */
        lRUCache = new DoubleLinked(2);
        lRUCache.put(2, 1);
        lRUCache.put(2, 2);
        lRUCache.get(2);
        lRUCache.put(1, 1);
        lRUCache.put(4, 1);
        lRUCache.get(2);
    }

    /**
     * ���ݴ�ͷ���룬����������head,������tail
     * ˫������ṹͼimg/146_LRUCache1.png
     * ע�⣺
     * 1��map��Ҫ��ʱ��������
     * 2��������Ϊ1�͵�һ��put����ʱ�ı߽�����
     * 3����β�ڵ㼰ʱ����
     */
    private static class DoubleLinked {
        public Node head;
        public Node tail;

        private int capacity;
        private int curSize;
        private Map<Integer, Node> map;

        public DoubleLinked(int capacity) {
            this.capacity = capacity;
            this.map = new HashMap<>();
            this.curSize = 0;
        }

        public int get(int key) {
            int val = -1;
            if (map.containsKey(key)) {
                Node node = map.get(key);
                val = node.value;// ���ص�ֵ
                if (curSize == 1 || node == tail) {
                    // ˵����ǰֻ��һ���ڵ�|ǡ����β��㣬��ľ��Ǹýڵ㣬���漰����
                    return val;
                } else if (node == head) {
                    // ��ǰ��ͷ��㣬��Ҫ��ͷ���ŵ�β���
                    head = node.next;
                    node.next = null;
                } else {
                    // �Ȳ���ͷ��㣬Ҳ����β���
                    node.last.next = node.next;
                    node.next.last = node.last;
                }
                head.last = null;
                tail.next = node;
                node.last = tail;
                tail = node;
            }
            return val;
        }

        public void put(int key, int value) {
            Node node = null;
            if (map.containsKey(key)) {
                node = map.get(key);
                node.value = value;// ������ͬһ��key����ֵͬ���������Ҫ��������ֵ
                if ((node == head && node == tail) || node == tail) {
                    // ��ǰֻ��һ���ڵ���ߵ�ǰ�ڵ���β���ڵ�
                    return;
                } else if (head == node) {
                    // ��ǰ�ڵ����ͷ���
                    head = head.next;
                    head.last = null;
                } else {
                    // ����ͷ�ڵ�Ҳ����β���
                    node.last.next = node.next;
                    node.next.last = node.last;
                }
                tail.next = node;
                node.last = tail;
                tail = node;
                return;
            }
            node = new Node(key, value);
            if (curSize == 0) {
                // ��һ�����ʱ
                head = tail = node;
                map.put(key, node);
                curSize++;
            } else if (curSize < capacity) {
                // ��δ����ֱ��ƴ�ӵ�ĩβ
                tail.next = node;
                node.last = tail;
                tail = node;
                map.put(key, node);
                curSize++;
            } else {
                // ��������
                int removeKey = head.key;
                map.remove(removeKey);// �Ƴ�head�ڵ�
                map.put(key, node); // �½ڵ�
                if (head == tail) {
                    // ��ǰֻʣһ���ڵ�
                    head = tail = node;
                    return;
                }
                head = head.next;
                head.last = null;
                tail.next = node;
                node.last = tail;
                tail = node;
            }
        }

        private static class Node {
            public int key;
            public int value;
            public Node last;
            public Node next;

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

    }

}
